﻿// Spun AJAX Framework
// Copyright (C) 2008 Blake Hegerle
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

using System;
using System.Collections.Generic;

namespace Formality
{
    public static class Recursion
    {
        #region One-method recursion
        public delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);

        public static Func<A, R> Combinator<A, R>(Func<Func<A, R>, Func<A, R>> f)
        {
            Recursive<A, R> rec = r => a => f(r(r))(a);
            return rec(rec);
        }
        #endregion

        #region Two-method recursion
        public delegate Func<A1, R1> Corecursive<A1, R1, A2, R2>(Corecursive<A1, R1, A2, R2> This, Corecursive<A2, R2, A1, R1> That);

        public static Pair<Func<A1, R1>, Func<A2, R2>>
            Cocombinator<A1, R1, A2, R2>(Func<Func<A1, R1>, Func<A2, R2>, Func<A1, R1>> f1, Func<Func<A2, R2>, Func<A1, R1>, Func<A2, R2>> f2)
        {
            Func<A1, R1> g1 = null;
            Func<A2, R2> g2 = null;

            g1 = f1(a => g1(a), a => g2(a));
            g2 = f2(a => g2(a), a => g1(a));

            return Pair.New(g1, g2);
        }

        public static Pair<Func<A1, R1>, Func<A2, R2>>
            Cocombinator<A1, R1, A2, R2>
        (
            Func<Func<A1, R1>, Func<A2, R2>, Func<A1, R1>> f1,
            Func<Func<A2, R2>, Func<A1, R1>, Func<A2, R2>> f2,
            Func<Func<A1, R1>, Func<A1, R1>> d1,
            Func<Func<A2, R2>, Func<A2, R2>> d2)
        {
            Func<A1, R1> g1 = null;
            Func<A2, R2> g2 = null;

            g1 = d1(f1(a => g1(a), a => g2(a)));
            g2 = d2(f2(a => g2(a), a => g1(a)));

            return Pair.New(g1, g2);
        }
        #endregion

        /*public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
        {
            return f.Memoize(new Dictionary<A, R>());
        }

        public static Func<A, R> Memoize<A, R>(this Func<A, R> f, R DefaultReturn)
        {
            return f.Memoize(new Dictionary<A, R>(), DefaultReturn);
        }*/

        public static Func<A, R> Memoize<A, R>(this Func<A, R> f, Dictionary<A, R> Map)
        {
            return Memoize(f, Map, default(R));
        }

        public static Func<A, R> Memoize<A, R>(this Func<A, R> f, Dictionary<A, R> Map, R DefaultReturn)
        {
            return a =>
            {
                R value;
                if (Map.TryGetValue(a, out value))
                    return value;

                Map[a] = DefaultReturn;
                value = f(a);
                Map[a] = value;
                return value;
            };
        }

        public static Func<A, R> MarkAndSweep<A, R>(this Func<A, R> f, R Default)
        {
            var Marked = new Set<A>();

            return a =>
            {
                if (Marked.Contains(a))
                    return Default;
                Marked.Add(a);
                return f(a);
            };
        }
    }
}
